package com.sam.sort;

import java.util.Arrays;

/**
 * 堆排序
 * Created by samwang on 2018/1/14.
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {24, 12, 41325, 463, 346, 13, 1235, 46, 346, 15, 5645, 7474};
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            buildHeap(array, array.length, i);
        }

        for (int i = array.length - 1; i >= 1; i--) {
            exchangeElement(array, 0, i);

            buildHeap(array, i, 0);
        }
        System.out.println(Arrays.toString(array));
    }


    public static void buildHeap(int[] array, int size, int index) {
        int leftIndex = index * 2 + 1;
        int rightIndex = index * 2 + 2;
        int largest = index;
        if (leftIndex < size && array[largest] < array[leftIndex]) {
            largest = leftIndex;
        }
        if (rightIndex < size && array[largest] < array[rightIndex]) {
            largest = rightIndex;
        }
        if (index != largest) {
            exchangeElement(array, index, largest);
            buildHeap(array, size, largest);
        }
    }


    private static void exchangeElement(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

}
